package pers.vic.basics.leetcode;

import javafx.scene.control.SplitPane;

/**
 * @author Vic.xu
 * @description:29. 两数相除  {@literal https://leetcode-cn.com/problems/divide-two-integers/}
 * @date: 2020/11/19  9:54
 */
public class J0029_M_Divide {
    /*
    给定两个整数，被除数 dividend 和除数 divisor。
    将两数相除，要求不使用乘法、除法和 mod 运算符。
    返回被除数 dividend 除以除数 divisor 得到的商。
    整数除法的结果应当截去（truncate）其小数部分，
    例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

     */
    /*
        网上的代码看的不大懂 只好自己瞎写了
        58/3=19...1
        58/48=1...10   3左移了四次得到48   1<<4 = 16   找到48 这个数，因为下一个96 已经大于58 了
        58 - 48 = 10;
        10/3=3...1    3 位移1次得到6       1<<1 = 2
        10 - 6 = 4
        4> 3 ,但是不需要位移              1<< 0 = 1
        结果 = 16 + 2 + 1 = 19

        总体就是小学的试试学的除法算法：
              _19___
            3) 58
              _30_
               28
              _27_
                1
     */
    public static int divide(int dividend, int divisor) {
        if (dividend == 0) {
            return 0;
        }

        if (divisor == 1) {
            return dividend;
        }
        if (divisor == -1) {
            if (dividend == Integer.MIN_VALUE) {
                return Integer.MAX_VALUE;
            }
            return -dividend;
        }

        int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = -1;
        }
        //不管边界了  不差这点位数
        long a = dividend > 0 ? dividend : -(long) dividend;
        long b = divisor > 0 ? divisor : -(long) divisor;
        if (a < b) {
            return 0;
        }
        int res = 0;
        //只要除数大于被除数 就继续尝试 减掉位移后的被除数
        while (a >= b) {
            long temp = b;
            //当前需要位移后的数字
            int track = 1;
            while (a >= (temp<<1)) {
                temp = temp << 1;
                track = track << 1;
            }

            a = a - temp;
            //结果加上当前位移后的值
            res += track;
        }
        return sign > 0 ? res : -res;
    }

    public static void main(String[] args) {
        System.out.println(Integer.MAX_VALUE);
        System.out.println(divide(-2147483648, 2));

    }
}
